package main.java.indi.zyj.hot100;

import main.java.indi.zyj.hot100.base.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class _01_pathSum {

    Map<Long, Integer> hashmap = null;
    int target;

    public int pathSum(TreeNode root, int targetSum) {

        hashmap = new HashMap<>();
        hashmap.put(0L, 1);
        target = targetSum;
        return reCur(root, 0L);

    }

    public int reCur(TreeNode root, Long preSum){

        if (root == null){
            return 0;
        }

        int res = 0;
        preSum += root.val;

        // res就是路径数量。curSum是根节点到当前节点的前缀和，
        // 如果哈希表中能找到之前存在过路径的前缀和为curSum - target，说明可以找到value条路径使其路径和为target。
        res += hashmap.getOrDefault(preSum - target, 0);
        // 将当前节点的前缀和加入map
        hashmap.put(preSum, hashmap.getOrDefault(preSum, 0) + 1);

        int left = reCur(root.left, preSum);
        int right = reCur(root.right, preSum);

        // 最后记得在哈希表中把已经找过的路径都去掉，即恢复状态。
        hashmap.put(preSum, hashmap.getOrDefault(preSum, 0) - 1);

        // 结果是当前节点前缀树的个数加上左边满足的个数加右边满足的个数
        return res + left + right;

    }

}
